package difficult.t135.candy;



/**
 * https://leetcode-cn.com/problems/candy/
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：
 * 1、每个孩子至少分配到 1 个糖果。
 * 2、相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 *
 * 想法：
 * 默认给1个，如果后一个数字大于前一个，则在前一个小朋友的基础上多给一个。
 * 如果后一个数字小于前一个，则后一个小朋友给一个糖果，如果前一个小朋友也是一个糖果，则必须给前一个小朋友加一个糖果，并依次向前维护关系，
 * 直到前一个小朋友数字不大于后一个或一直维护到第一个小朋友，维护结束。
 *
 * 执行用时：483 ms, 在所有 Java 提交中击败了5.02%的用户
 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了89.82%的用户
 *
 * @Author luxiaoxiao
 * @Date 2022/1/10
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        // [1,3,2,2,1]
        int[] ratings = new int[]{1, 3, 2, 2, 1};
        int sum = solution.candy(ratings);
        System.out.println(sum);
    }


    /**
     * 计算最小糖果数
     *
     * @Author luxiaoxiao
     * @Date 2022/1/10
     */
    public int candy(int[] ratings) {
        // 用来记录每个小朋友分到的糖果数量
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            } else {
                candies[i] = 1;
                keepRelation(ratings, candies, i);
            }
        }

        int sum = 0;
        for (int num : candies) {
            sum += num;
        }
        return sum;
    }


    /**
     * 保证相邻两个孩子评分更高的孩子会获得更多的糖果
     *
     * @Author luxiaoxiao
     * @Date 2022/1/10
     */
    private void keepRelation(int[] ratings, int[] candies, int index) {
        while (index >= 1) {
            if (ratings[index - 1] <= ratings[index]) {
                break;
            } else {
                if (candies[index - 1] <= candies[index]) {
                    candies[index - 1]++;
                }
                index--;
            }
        }
    }
}
